#include <math.h>
#include <stdio.h>
#include <vector>

typedef unsigned int uint;

//imitation of given framework
namespace CMainFrame {

void RecursiveIEPF(int start, int end);
// float dist(float ux, float uy, float vx, float vy, float px, float py);

struct Point {
    Point() {}
    Point(float x, float y) : x(x), y(y) {}
    float x;
    float y;
};

struct Edge {
    float x1;
    float y1;
    float x2;
    float y2;
};

struct ScannerDummy {
    std::vector<Point> cartesData;
    std::vector<Edge> world;
};

ScannerDummy *Scanner;

int NumberOfPoints = 3;
float EdgeThreshold = 1.1;
int NumberOfEdges = 0; //this is probably within ScannerDummy?
//imitation end

}

//our stuff starts here
inline float dist2(const float ux, const float uy, const float vx, const float vy,
    const float px, const float py) {
    const float vu_x = vx - ux;
    const float vu_y = vy - uy;

    const float pu_x = px - ux;
    const float pu_y = py - uy;

    float norm = sqrt(vu_x * vu_x + vu_y * vu_y);
    float crossP = vu_x * pu_y - vu_y * pu_x;

    return fabs(crossP / norm);
}

inline float dist(const float ux, const float uy, const float vx, const float vy,
    const float px, const float py) {

    const float vu_x = vx - ux;
    const float vu_y = vy - uy;

    const float pu_x = px - ux;
    const float pu_y = py - uy;

    float normSquared = vu_x * vu_x + vu_y * vu_y;
    float dotP = pu_x * vu_x + pu_y * vu_y;

    float dx = pu_x - (dotP / normSquared) * vu_x;
    float dy = pu_y - (dotP / normSquared) * vu_y;

    return sqrt(dx * dx + dy * dy);
}

void CMainFrame::RecursiveIEPF(int start, int end) {
    const float ux = Scanner->cartesData[start].x;
    const float uy = Scanner->cartesData[start].y;
    const float vx = Scanner->cartesData[end].x;
    const float vy = Scanner->cartesData[end].y;

    float maxDist = 0;
    int maxDistIndex = start;
    for (uint i = start + 1; i < end; i++) {
        float d = dist(ux, uy, vx, vy,
            Scanner->cartesData[i].x,
            Scanner->cartesData[i].y);
        printf("%d-%d: %d, %.2f\n", start, end, i, d);
        if (d > maxDist) {
            maxDist = d;
            maxDistIndex = i;
        }
    }

    if (maxDist <= EdgeThreshold && (end - start + 1) >= NumberOfPoints) {
        Scanner->world[NumberOfEdges].x1 = ux;
        Scanner->world[NumberOfEdges].y1 = uy;
        Scanner->world[NumberOfEdges].x2 = vx;
        Scanner->world[NumberOfEdges].y2 = vy;
        NumberOfEdges++;
    } else if (maxDist > EdgeThreshold) {
        RecursiveIEPF(start, maxDistIndex);
        RecursiveIEPF(maxDistIndex, end);
    }
}

//typedef CMainFrame::Scanner S;
using namespace CMainFrame;
int main() {
    Scanner = new ScannerDummy();
    Scanner->cartesData = std::vector<Point>(7);
    Scanner->cartesData[0] = Point(0,0);
    Scanner->cartesData[1] = Point(0,1);
    Scanner->cartesData[2] = Point(1,2);
    Scanner->cartesData[3] = Point(5,3);
    Scanner->cartesData[4] = Point(0,4);
    Scanner->cartesData[5] = Point(1,5);
    Scanner->cartesData[6] = Point(0,6);
    //at most, there'll be n-1 edges
    Scanner->world = std::vector<Edge>(Scanner->cartesData.size() - 1);

    RecursiveIEPF(0, Scanner->cartesData.size() - 1);

    for (uint i = 0; i < NumberOfEdges; i++) {
        printf("(%.2f,%.2f)-(%.2f,%.2f)\n",
            Scanner->world[i].x1, Scanner->world[i].y1,
            Scanner->world[i].x2, Scanner->world[i].y2);
    }

    delete Scanner;
    return 0;
}
